package top.minuy.structure.graph.bridge;

import top.minuy.structure.graph.representations.Edge;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 图，寻找桥
 *
 * @author Minuy
 * @time 20:27
 * @date 2021/11/21
 */
public class FindBridges {
    private List<Edge> edges;
    private Graph g;
    private int[] ord; // 遍历顺序数组
    private int[] low; // 与之相连的非父顶点的最小顺序
    private boolean[] isVisited; // 是否被遍历
    private int count; // 遍历计数

    public FindBridges(Graph g) {
        this.g = g;

        ord = new int[g.V()];
        low = new int[g.V()];
        isVisited = new boolean[g.V()];
        edges = new ArrayList<>();

        count = 0;

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                dfs(v, v);
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param v      当前遍历的顶点
     * @param parent 父顶点
     */
    private void dfs(int v, int parent) {
        // 设置默认信息
        isVisited[v] = true;
        ord[v] = count;
        low[v] = ord[v];

        // 遍历计数加一
        count++;
        for (int w : g.adj(v)) {

            // 正常的深度优先遍历
            if (!isVisited[w]) {
                dfs(w, v);
            }

            // 如果子顶点low值更小，说明能通过其他的路访问到自己之前的顶点
            // 如果子顶点low值不变，说明能通过其他的路访问到自己
            if (w != parent) {
                low[v] = Math.min(low[v], low[w]);
            }

            // 检测出桥了
            // 子顶点默认的low值比自己大，如若遍历后low值还是不变，
            // 则说明不能通过另外的路访问到自己或自己之前的节点，
            // 此边断开后彻底与子顶点失去了联系，故为桥，记录之

            // isVisited为true的，那只有两种情况，一种是父顶点，还有就是环
            // 父顶点也算其相邻顶点，需要排除
            // 所以判定为桥的只是在没有看过（isVisited为false）的情况中出现
            if ((w != parent) /*&& (low[w] > low[v])*/) {
                // BUG : 解决了近一个小时，耗费33根头发，
                // 这里不应该是大于自己的low就是桥了，而是大于自己的ord
                // 因为自己的low可以被之前的顶点变小，会导致误判，ord不会
                // 而子顶点默认的low是比自己的ord大的，一旦low变小，
                // 则说明能回到祖先顶点或者自己了
                // 那么变小就至少不是low[w]>ord[v]了
                if(low[w]>ord[v]){
                edges.add(new Edge(v, w));}
            }
        }
    }

    public Iterable<Edge> bridges() {
        return edges;
    }

//
//    private Graph G;
//    private boolean[] visited;
//
//    private int ord[];
//    private int low[];
//    private int cnt;
//
//    private ArrayList<Edge> res;
//
//    public FindBridges(Graph G){
//
//        this.G = G;
//        visited = new boolean[G.V()];
//
//        res = new ArrayList<>();
//        ord = new int[G.V()];
//        low = new int[G.V()];
//        cnt = 0;
//
//        for(int v = 0; v < G.V(); v ++)
//            if(!visited[v])
//                dfs(v, v);
//    }
//
//    private void dfs(int v, int parent){
//
//        visited[v] = true;
//        ord[v] = cnt;
//        low[v] = ord[v];
//        cnt ++;
//
//        for(int w: G.adj(v))
//            if(!visited[w]){
//                dfs(w, v);
//                low[v] = Math.min(low[v], low[w]);
//                if(low[w] > ord[v])
//                    res.add(new Edge(v, w));
//            }
//            else if(w != parent)
//                low[v] = Math.min(low[v], low[w]);
//    }
//
//    public ArrayList<Edge> bridges(){
//        return res;
//    }
}
